P1344 [USACO4.4]追查坏牛奶Pollutant Control[最小割]

2017-07-09

题目描述

你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶。很不幸，你发现这件事的时候，有三聚氰胺的牛奶已经进入了送货网。
这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。

在追查这些有三聚氰胺的牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。你的任务是，在保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。

输入输出格式

输入格式：

第一行: 两个整数N(2<=N<=32)、M(0<=M<=1000), N表示仓库的数目，M表示运输卡车的数量。仓库1代表发货工厂，仓库N代表有三聚氰胺的牛奶要发往的零售商。第2..M+1行: 每行3个整数Si,Ei,Ci。其中Si,Ei表示这辆卡车的出发仓库，目的仓库。Ci(0 <= C i <= 2,000,000) 表示让这辆卡车停止运输的损失。

输出格式：

两个整数C、T：C表示最小的损失，T表示在损失最小的前提下，最少要停止的卡车数。
usaco的第二问:
接下来T行表示你要停止哪几条线路。如果有多种方案使损失最小，输出停止的线路最少的方案。如果仍然还有相同的方案，请选择开始输入顺序最小的。

输入输出样例

输入样例#1：

4 5
1 3 100
3 2 50
2 4 60
1 2 40
2 3 80

输出样例#1：

60 1
3

题解

第一问:求最大流(最小割最大流一样的)
然后把边权从大到小排序(因为要使停止的路线最少)
一条一条边去判断,如果删去该边之后,减小的最大流等于该边的边权(也就是损失),那么就删了这条边.
//删了之后记得减去
从x到y可以有很多条不同的路，所以在删边时不能直接赋成0，而是减掉这条边的边权。

/*
ID: ylx14271
PROG: milk6
LANG: C++
 */
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int read()
{
    char s;int k=0,base=1;
    while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
    if(s==EOF)exit(0);
    if(s=='-')base=-1,s=getchar();
    while(s>='0'&&s<='9'){k=k*10+(s-'0');s=getchar();}
    return k*base;
}
void write(int x)
{
    if(x<0){putchar('-');write(-x);}
    else{if(x/10)write(x/10);putchar(x%10+'0');}
}
int pre[100];
int n,m;
struct node
{
    int u,v,w;//w:损失
    int id;
} a[3000];
int f[50][50];//流量(损失
int c[50][50];
int p[100],a1;
int u1,v1,c1;
int q[4000];
void add(int uu,int vv,int ww)//连两条边,一条正的边和一条反向边
{
    f[uu][vv]+=ww;//加到uu→vv这条边上去
    a1++;
    a[a1].id=a1;
    a[a1].u=uu;a[a1].v=vv;a[a1].w=ww;//存起来
}
int w[4000],d1;
int cmp(node aa,node bb)
{
    if (aa.w==bb.w) return aa.id<bb.id;
    return aa.w>bb.w;
}
int spfa(int x)
{
    memcpy(c,f,sizeof(c));//c存f数组的东西
    c[a[x].u][a[x].v]-=a[x].w;//删掉这条边
    int ans1=0;
    while (true)//搜到 搜不到路径
    {
        int l=0,r=1;q[1]=1;
        memset(pre,-1,sizeof(pre));//初始化
        while (l<r)
        {
            l++;
            int x1=q[l];
            //cout<<x1<<" ";
            for (int i=1;i<=n;i++)
            {
                if (c[x1][i]>0&&pre[i]==-1)//没被走过(没有前驱)并且流量<容量
                {
                    pre[i]=x1;//标记
                    r++;q[r]=i;//入队
                }
            }
            if (pre[n]>0) break;//搜完了
        }
        //cout<<endl;
        if (pre[n]==-1) break; //找不到就退掉
        int mi=233333333;
        for (int i=n;i>1;i=pre[i]) mi=min(mi,c[pre[i]][i]);//找瓶颈
        for (int i=n;i>1;i=pre[i]) c[pre[i]][i]-=mi;//减去
        ans1+=mi;
        //cout<<"---   "<<mi<<"   \n";
    }
    return ans1;
}
int main()
{
    freopen("milk6.in","r",stdin);
    freopen("milk6.out","w",stdout);
    n=read();
    m=read();
    a1=0;
    for (int i=1;i<=m;i++)//建图
    {
        u1=read();v1=read();c1=read();
        add(u1,v1,c1);
    }
    int xxx=spfa(0);//找最大流
    printf("%d ",xxx);
    d1=0;
    int s1=0;
    sort(a+1,a+m+1,cmp);
    for (int j=1;j<=m;j++)//一条一条边的删
    {
        s1=spfa(j);
        if (s1+a[j].w==xxx)    
        {
            f[a[j].u][a[j].v]-=a[j].w;//开始没写这句然后炸了
            d1++;//存起来
            w[d1]=a[j].id;
            xxx=s1;
        }
    }
    printf("%d\n",d1);
    sort(w+1,w+d1+1);//从小到大排序
    for (int i=1;i<=d1;i++) printf("%d\n",w[i]);
    return 0;
}